{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Wilkinson-type polynomials"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Wilkinson-type polynomials](http://en.wikipedia.org/wiki/Wilkinson%27s_polynomial) are of the form\n",
    "\n",
    "$$W_n(x) = (x-1) \\cdot (x-2) \\cdot \\cdots \\cdot (x-n).$$ \n",
    "\n",
    "It is well known that it is difficult to calculate the roots of these polynomials. We will investigate how well the `newton` function in the `ValidatedNumerics.jl` package is able to calculate their roots."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We use the `Polynomials` package to calculate the coefficients:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "using Polynomials"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "wilkinson_coefficients (generic function with 1 method)"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function wilkinson_coefficients(n)\n",
    "    p = poly(collect(1:n))  # define a polynomial by its roots\n",
    "    p.a  # the coefficients\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For example, $W_2$ is given by $W_2(x) = 2 - 3x + x^2$; note the order of the coefficients:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3-element Array{Int64,1}:\n",
       "  2\n",
       " -3\n",
       "  1"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "wilkinson_coefficients(2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Horner's method](http://en.wikipedia.org/wiki/Horner%27s_method) is an efficient method for evaluating polynomials. For $W_2$, the idea is to rewrite the polynomial as \n",
    "\n",
    "$W_2(x) = (x + 3)\\cdot x + 2,$\n",
    "\n",
    "so that no explicit powers remain."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Generating the polynomials "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For convenience, we repeat here code from `test/root_finding_tests/wilkinson_polynomials.jl` to generate efficient versions of the Wilkinson polynomials using metaprogramming to implement Horner's rule"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "generate_wilkinson_horner (generic function with 1 method)"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function generate_wilkinson_horner(n)\n",
    "    coeffs = wilkinson_coefficients(n)\n",
    "\n",
    "    expr = :($(coeffs[end]))  # start with highest power\n",
    "\n",
    "    for i in length(coeffs)-1:-1:1\n",
    "        expr = :($expr*x + $(coeffs[i]))\n",
    "    end\n",
    "\n",
    "    expr\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For example, the code generated for $W_3$ is"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":(((1x + -6) * x + 11) * x + -6)"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "generate_wilkinson_horner(3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We now generate various Wilkinson polynomials:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "function subscriptify(n::Int)\n",
    "    subscript_digits = [c for c in \"₀₁₂₃₄₅₆₇₈₉\"]\n",
    "    dig = reverse(digits(n))\n",
    "    join([subscript_digits[i+1] for i in dig])\n",
    "end\n",
    "\n",
    "for n in 1:15\n",
    "    fn_name = symbol(string(\"W\", subscriptify(n)))\n",
    "    expr = generate_wilkinson_horner(n)\n",
    "\n",
    "    @eval $(fn_name)(x) = $(expr)\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can now refer to the polynomials using `W₁`, `W₂`, etc.:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6-element Array{Int64,1}:\n",
       "  -6\n",
       "   0\n",
       "   0\n",
       "   0\n",
       "   6\n",
       " 504"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = [0, 1, 2, 3, 4, 10]\n",
    "map(W₃, x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We see that indeed `W₃` has roots at $1$, $2$ and $3$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Rigorous root finding"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can now apply the `newton` function from `ValidatedNumerics` to search for roots of the function within a given interval as follows. (In the following, it is necessary to run certain cells twice to eliminate the compilation overhead in the timings.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "using ValidatedNumerics"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "elapsed time: 1.630687196 seconds (54897236 bytes allocated, 4.59% gc time)\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "3-element Array{(Interval{Float64},Symbol),1}:\n",
       " ([0.9999999999999994, 1.0000000000000009],:unique)\n",
       " ([1.999999999999999, 2.0000000000000027],:unique) \n",
       " ([2.999999999999997, 3.0000000000000004],:unique) "
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "@time roots = newton(W₃, @interval(-10, 10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We see that `newton` correctly finds the roots; it also *guarantees* that they are unique, i.e. that there is exactly one root in the given interval. We can obtain higher precision by changing the precision in the calculation:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "elapsed time: 1.017732564 seconds (14999856 bytes allocated)\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "3-element Array{(Interval{BigFloat},Symbol),1}:\n",
       " ([9.999999999999999999999999999999999999999999999999999999999999999999999999999568e-01, 1.000000000000000000000000000000000000000000000000000000000000000000000000000069e+00]₂₅₆,:unique)\n",
       " ([1.999999999999999999999999999999999999999999999999999999999999999999999999999914e+00, 2.000000000000000000000000000000000000000000000000000000000000000000000000000207e+00]₂₅₆,:unique)\n",
       " ([2.999999999999999999999999999999999999999999999999999999999999999999999999999758e+00, 3.000000000000000000000000000000000000000000000000000000000000000000000000000035e+00]₂₅₆,:unique)"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "setprecision(Interval, 256)\n",
    "@time roots2 = newton(W₃, @interval(-10, 10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Or we can reuse the results found previously with the lower precision:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "elapsed time: 0.168942833 seconds (2898596 bytes allocated)\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "3-element Array{(Interval{BigFloat},Symbol),1}:\n",
       " ([1e+00, 1e+00]₂₅₆,:unique)                                                                                                                                                              \n",
       " ([2e+00, 2e+00]₂₅₆,:unique)                                                                                                                                                              \n",
       " ([2.999999999999999999999999999999999999999999999999999999999999999999999999999758e+00, 3.000000000000000000000000000000000000000000000000000000000000000000000000000035e+00]₂₅₆,:unique)"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "setprecision(Interval, 256)\n",
    "@time roots3 = newton(W₃, roots)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's try with a more challenging case. For `Float64`, using the `:wide` rounding is much faster:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "elapsed time: 5.750922701 seconds (1619874936 bytes allocated, 27.49% gc time)\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "10-element Array{(Interval{Float64},Symbol),1}:\n",
       " ([0.999999999999997, 1.0000000000000042],:unique) \n",
       " ([1.9999999999997027, 2.0000000000002287],:unique)\n",
       " ([2.9999999999975757, 3.000000000003865],:unique) \n",
       " ([3.9999999999716045, 4.000000000029477],:unique) \n",
       " ([4.99999999982392, 5.0000000001432605],:unique)  \n",
       " ([5.999999999690147, 6.000000000378698],:unique)  \n",
       " ([6.999999999507423, 7.000000000780629],:unique)  \n",
       " ([7.999999999455639, 8.00000000084168],:unique)   \n",
       " ([8.999999999350004, 9.000000000346732],:unique)  \n",
       " ([9.999999999923057, 10.000000000090695],:unique) "
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "setprecision(Interval, Float64)\n",
    "setrounding(Interval, :narrow)\n",
    "@time roots = newton(W₁₀, @interval(-20, 20))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "elapsed time: 0.602897027 seconds (136606384 bytes allocated, 27.03% gc time)\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "10-element Array{(Interval{Float64},Symbol),1}:\n",
       " ([0.9999999999999781, 1.000000000000022],:unique) \n",
       " ([1.9999999999986873, 2.0000000000015774],:unique)\n",
       " ([2.9999999999769145, 3.00000000002351],:unique)  \n",
       " ([3.9999999998149893, 4.000000000198532],:unique) \n",
       " ([4.9999999993051, 5.000000000881577],:unique)    \n",
       " ([5.999999997587125, 6.000000002318674],:unique)  \n",
       " ([6.999999995966628, 7.000000003814153],:unique)  \n",
       " ([7.999999996382491, 8.000000004036211],:unique)  \n",
       " ([8.999999998178597, 9.000000001849779],:unique)  \n",
       " ([9.999999999564606, 10.000000000468848],:unique) "
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "setprecision(Interval, Float64)\n",
    "setrounding(Interval, :wide)\n",
    "@time roots = newton(W₁₀, @interval(-20, 20))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using directly higher precision is rather costly:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "elapsed time: 27.047184688 seconds (2373800544 bytes allocated, 49.94% gc time)\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "10-element Array{(Interval{BigFloat},Symbol),1}:\n",
       " ([9.999999999999999999999999999999999999999999999999999999999999999999999999982555e-01, 1.000000000000000000000000000000000000000000000000000000000000000000000000001986e+00]₂₅₆,:unique)\n",
       " ([1.999999999999999999999999999999999999999999999999999999999999999999999999897851e+00, 2.000000000000000000000000000000000000000000000000000000000000000000000000132513e+00]₂₅₆,:unique)\n",
       " ([2.999999999999999999999999999999999999999999999999999999999999999999999998161947e+00, 3.000000000000000000000000000000000000000000000000000000000000000000000001994126e+00]₂₅₆,:unique)\n",
       " ([3.999999999999999999999999999999999999999999999999999999999999999999999986277439e+00, 4.00000000000000000000000000000000000000000000000000000000000000000000001396503e+00]₂₅₆,:unique) \n",
       " ([4.999999999999999999999999999999999999999999999999999999999999999999999933772609e+00, 5.000000000000000000000000000000000000000000000000000000000000000000000064709913e+00]₂₅₆,:unique)\n",
       " ([5.999999999999999999999999999999999999999999999999999999999999999999999812336334e+00, 6.000000000000000000000000000000000000000000000000000000000000000000000185915499e+00]₂₅₆,:unique)\n",
       " ([6.999999999999999999999999999999999999999999999999999999999999999999999686873877e+00, 7.000000000000000000000000000000000000000000000000000000000000000000000298166897e+00]₂₅₆,:unique)\n",
       " ([7.999999999999999999999999999999999999999999999999999999999999999999999723217154e+00, 8.000000000000000000000000000000000000000000000000000000000000000000000280624352e+00]₂₅₆,:unique)\n",
       " ([8.999999999999999999999999999999999999999999999999999999999999999999999864519933e+00, 9.000000000000000000000000000000000000000000000000000000000000000000000140370073e+00]₂₅₆,:unique)\n",
       " ([9.999999999999999999999999999999999999999999999999999999999999999999999964236037e+00, 1.000000000000000000000000000000000000000000000000000000000000000000000003457259e+01]₂₅₆,:unique)"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "setprecision(Interval, 256)\n",
    "@time roots2 = newton(W₁₀, @interval(-20, 20))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Whereas reusing the previously-found roots is, of course, much faster:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "elapsed time: 0.02859459 seconds (6755144 bytes allocated)\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "10-element Array{(Interval{BigFloat},Symbol),1}:\n",
       " ([9.999999999999999999999999999999999999999999999999999999999999999999999999981691e-01, 1.00000000000000000000000000000000000000000000000000000000000000000000000000171e+00]₂₅₆,:unique) \n",
       " ([1.999999999999999999999999999999999999999999999999999999999999999999999999890355e+00, 2.000000000000000000000000000000000000000000000000000000000000000000000000109645e+00]₂₅₆,:unique)\n",
       " ([2.999999999999999999999999999999999999999999999999999999999999999999999998081009e+00, 3.000000000000000000000000000000000000000000000000000000000000000000000001815703e+00]₂₅₆,:unique)\n",
       " ([3.999999999999999999999999999999999999999999999999999999999999999999999986651765e+00, 4.000000000000000000000000000000000000000000000000000000000000000000000014338872e+00]₂₅₆,:unique)\n",
       " ([4.999999999999999999999999999999999999999999999999999999999999999999999938941667e+00, 5.000000000000000000000000000000000000000000000000000000000000000000000062004858e+00]₂₅₆,:unique)\n",
       " ([5.999999999999999999999999999999999999999999999999999999999999999999999804832056e+00, 6.00000000000000000000000000000000000000000000000000000000000000000000017982548e+00]₂₅₆,:unique) \n",
       " ([6.999999999999999999999999999999999999999999999999999999999999999999999692673789e+00, 7.000000000000000000000000000000000000000000000000000000000000000000000295631387e+00]₂₅₆,:unique)\n",
       " ([7.999999999999999999999999999999999999999999999999999999999999999999999696081483e+00, 8.000000000000000000000000000000000000000000000000000000000000000000000264270074e+00]₂₅₆,:unique)\n",
       " ([8.999999999999999999999999999999999999999999999999999999999999999999999852277853e+00, 9.000000000000000000000000000000000000000000000000000000000000000000000149859909e+00]₂₅₆,:unique)\n",
       " ([9.999999999999999999999999999999999999999999999999999999999999999999999965533397e+00, 1.000000000000000000000000000000000000000000000000000000000000000000000003311687e+01]₂₅₆,:unique)"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "setprecision(Interval, 256)\n",
    "@time roots3 = newton(W₁₀, roots)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "However, for very difficult polynomials, even with `Float64` the method starts to suffer. We use the `clean_roots` function to remove identical roots, but even then, there are, for some reason, several almost-repeated roots:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "elapsed time: 2.890292212 seconds (943686744 bytes allocated, 30.37% gc time)\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "60-element Array{(Interval{Float64},Symbol),1}:\n",
       " ([0.9999999999999738, 1.000000000000032],:unique)  \n",
       " ([1.9999999999968605, 2.000000000003299],:unique)  \n",
       " ([2.999999999937011, 3.0000000000693854],:unique)  \n",
       " ([3.9999999992490975, 4.00000000077714],:unique)   \n",
       " ([4.999999993998892, 5.0000000058092455],:unique)  \n",
       " ([5.999999972275639, 6.000000028158782],:unique)   \n",
       " ([6.999999857327201, 7.000000098943499],:unknown)  \n",
       " ([6.9999998573272, 7.0000000989435],:unknown)      \n",
       " ([6.999999857327201, 7.000000098943499],:unknown)  \n",
       " ([6.999999857327202, 7.000000098943498],:unknown)  \n",
       " ([7.999999725661288, 8.000000258515469],:unknown)  \n",
       " ([7.999999725661287, 8.00000025851547],:unknown)   \n",
       " ([7.999999725661288, 8.000000258515469],:unknown)  \n",
       " ⋮                                                  \n",
       " ([9.999999645289092, 10.000000170076977],:unknown) \n",
       " ([9.999999645289094, 10.000000170076975],:unknown) \n",
       " ([9.999999645289092, 10.000000170076977],:unknown) \n",
       " ([9.999999645289105, 10.000000170076964],:unknown) \n",
       " ([9.999999645289103, 10.000000170076966],:unknown) \n",
       " ([9.999999645289105, 10.000000170076964],:unknown) \n",
       " ([9.99999964528911, 10.000000170076959],:unknown)  \n",
       " ([10.999999942608941, 10.999999968904618],:unknown)\n",
       " ([10.99999996890448, 10.999999995200257],:unknown) \n",
       " ([10.999999995200069, 11.000000021495845],:unknown)\n",
       " ([11.000000021495657, 11.000000047791433],:unknown)\n",
       " ([11.999999992524769, 12.000000007143052],:unique) "
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "setprecision(Interval, Float64)\n",
    "setrounding(Interval, :wide)\n",
    "@time roots = newton(W₁₂, @interval(-20, 20))\n",
    "roots = ValidatedNumerics.clean_roots(roots)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We see that the method is unable to resolve several of the roots, and for some reason gives lots of similar, repeated intervals. We can increase the precision as follows, but even using the `clean_roots` function, we still have many repeated roots:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "elapsed time: 2.106868243 seconds (161580440 bytes allocated, 59.87% gc time)\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "50-element Array{(Interval{BigFloat},Symbol),1}:\n",
       " ([9.999999999999999999999999999999999999999999999999999999999999999999999999975473e-01, 1.000000000000000000000000000000000000000000000000000000000000000000000000002366e+00]₂₅₆,:unique)\n",
       " ([1.999999999999999999999999999999999999999999999999999999999999999999999999764993e+00, 2.000000000000000000000000000000000000000000000000000000000000000000000000245854e+00]₂₅₆,:unique)\n",
       " ([2.999999999999999999999999999999999999999999999999999999999999999999999994929464e+00, 3.000000000000000000000000000000000000000000000000000000000000000000000005324129e+00]₂₅₆,:unique)\n",
       " ([3.999999999999999999999999999999999999999999999999999999999999999999999937344597e+00, 4.000000000000000000000000000000000000000000000000000000000000000000000058873728e+00]₂₅₆,:unique)\n",
       " ([4.99999999999999999999999999999999999999999999999999999999999999999999957930183e+00, 5.000000000000000000000000000000000000000000000000000000000000000000000455049532e+00]₂₅₆,:unique) \n",
       " ([5.999999999999999999999999999999999999999999999999999999999999999999998289307937e+00, 6.0000000000000000000000000000000000000000000000000000000000000000000017348676e+00]₂₅₆,:unique)  \n",
       " ([6.999999999999999999999999999999999999999999999999999999999999999999994717476021e+00, 7.00000000000000000000000000000000000000000000000000000000000000000000513411087e+00]₂₅₆,:unique) \n",
       " ([6.999999999999999999999999999999999999999999999999999999999999999999994822307845e+00, 7.000000000000000000000000000000000000000000000000000000000000000000005256356596e+00]₂₅₆,:unique)\n",
       " ([6.999999999999999999999999999999999999999999999999999999999999999999994899012015e+00, 7.000000000000000000000000000000000000000000000000000000000000000000005525577958e+00]₂₅₆,:unique)\n",
       " ([6.999999999999999999999999999999999999999999999999999999999999999999994899012084e+00, 7.000000000000000000000000000000000000000000000000000000000000000000005525577889e+00]₂₅₆,:unique)\n",
       " ([7.999999999999999999999999999999999999999999999999999999999999999999990665382833e+00, 8.000000000000000000000000000000000000000000000000000000000000000000009332907137e+00]₂₅₆,:unique)\n",
       " ([7.999999999999999999999999999999999999999999999999999999999999999999990891866975e+00, 8.000000000000000000000000000000000000000000000000000000000000000000008848659617e+00]₂₅₆,:unique)\n",
       " ([7.999999999999999999999999999999999999999999999999999999999999999999990911681317e+00, 8.000000000000000000000000000000000000000000000000000000000000000000008693706441e+00]₂₅₆,:unique)\n",
       " ⋮                                                                                                                                                                                        \n",
       " ([8.999999999999999999999999999999999999999999999999999999999999999999990752837996e+00, 9.000000000000000000000000000000000000000000000000000000000000000000010522281514e+00]₂₅₆,:unique)\n",
       " ([8.999999999999999999999999999999999999999999999999999999999999999999990752839101e+00, 9.000000000000000000000000000000000000000000000000000000000000000000010522280408e+00]₂₅₆,:unique)\n",
       " ([9.999999999999999999999999999999999999999999999999999999999999999999992679846183e+00, 1.000000000000000000000000000000000000000000000000000000000000000000000669176436e+01]₂₅₆,:unique)\n",
       " ([9.999999999999999999999999999999999999999999999999999999999999999999992737306827e+00, 1.000000000000000000000000000000000000000000000000000000000000000000000666267346e+01]₂₅₆,:unique)\n",
       " ([9.999999999999999999999999999999999999999999999999999999999999999999992737306965e+00, 1.000000000000000000000000000000000000000000000000000000000000000000000666267332e+01]₂₅₆,:unique)\n",
       " ([9.99999999999999999999999999999999999999999999999999999999999999999999281911359e+00, 1.000000000000000000000000000000000000000000000000000000000000000000000749767448e+01]₂₅₆,:unique) \n",
       " ([9.999999999999999999999999999999999999999999999999999999999999999999992857780411e+00, 1.000000000000000000000000000000000000000000000000000000000000000000000710108089e+01]₂₅₆,:unique)\n",
       " ([9.999999999999999999999999999999999999999999999999999999999999999999993040980215e+00, 1.000000000000000000000000000000000000000000000000000000000000000000000710201138e+01]₂₅₆,:unique)\n",
       " ([9.999999999999999999999999999999999999999999999999999999999999999999993040980353e+00, 1.000000000000000000000000000000000000000000000000000000000000000000000710201125e+01]₂₅₆,:unique)\n",
       " ([9.999999999999999999999999999999999999999999999999999999999999999999993061431353e+00, 1.00000000000000000000000000000000000000000000000000000000000000000000077233044e+01]₂₅₆,:unique) \n",
       " ([1.099999999999999999999999999999999999999999999999999999999999999999999699198822e+01, 1.100000000000000000000000000000000000000000000000000000000000000000000309166875e+01]₂₅₆,:unique)\n",
       " ([1.199999999999999999999999999999999999999999999999999999999999999999999942951958e+01, 1.200000000000000000000000000000000000000000000000000000000000000000000054277974e+01]₂₅₆,:unique)"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "setprecision(Interval, 256)\n",
    "@time roots2 = newton(W₁₂, roots)\n",
    "roots2 = ValidatedNumerics.clean_roots(roots2)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 0.3.9-pre",
   "language": "julia",
   "name": "julia-0.3"
  },
  "language_info": {
   "name": "julia",
   "version": "0.3.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}
